/*
 * @lc app=leetcode.cn id=380 lang=cpp
 *
 * [380] O(1) 时间插入、删除和获取随机元素
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class RandomizedSet {
    set<int> s;
public:
    RandomizedSet() {

    }
    
    bool insert(int val) {
        if(s.find(val) == s.end())
        {
            s.insert(val);
            return true;
        }
        return false;
    }
    
    bool remove(int val) {
        auto it = s.find(val);
        if(it == s.end())
            return false;
        s.erase(it);
        return true;
    }
    
    int getRandom() {
        auto it = s.begin();
        int n = rand() % s.size();
        while (n--)
        {
            it++;
        }
        return *it;
    }
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet* obj = new RandomizedSet();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
// @lc code=end

// int main(int argc, char const *argv[])
// {
//     RandomizedSet s;
//     cout << s.insert(1) << endl;
//     cout << s.remove(2) << endl;
//     cout << s.insert(2) << endl;
//     cout << s.getRandom() << endl;
//     cout << s.remove(1) << endl;
//     cout << s.insert(2) << endl;
//     cout << s.getRandom() << endl;
//     return 0;
// }
